
<!DOCTYPE html>
<html>

	<head>
	<title>CAIJL's Blog</title>
	<meta charset="utf-8"/>
	<link rel="stylesheet" href="/font-awesome-4.7.0/css/font-awesome.min.css">

	<link rel="stylesheet" href="/bootstrap-3.3.7/css/bootstrap.min.css">
	<script src="/jquery-2.1.1/jquery.min.js"></script>
	<script src="/bootstrap-3.3.7/js/bootstrap.min.js"></script>

	<link rel="stylesheet" href="/css/bootstrap-slider.min.css">
	<script src="/js/bootstrap-slider.min.js"></script>
	
	<link rel="stylesheet" href="/css/main.css">
	<script src="/js/main.js"></script>
	
	<link rel="stylesheet" href="/css/cursor.css">
	<script src="/js/cursor.js"></script>
	
	
	<link rel="stylesheet" href="/css/code.css">
	<!--link rel="stylesheet" href="/css/markdown.css"-->
	
	<link rel="stylesheet" href="/css/head.css">

	<script src="/js/window.js"></script>
	<script src='//unpkg.com/valine/dist/Valine.min.js'></script>
	</head>
<body>

	<link rel="stylesheet" href="/katex/katex.min.css" crossorigin="anonymous">
	<script src="/katex/katex.min.js" crossorigin="anonymous"></script>
	<script src="/katex/contrib/mathtex-script-type.min.js" defer></script>
	<script defer src="/katex/contrib/auto-render.min.js"crossorigin="anonymous"
	    onload="renderMathInElement(document.body);"></script>
	<script>document.addEventListener("DOMContentLoaded", function() {renderMathInElement(document.body,{"delimiters":[{left: "$", right: "$", display: false}]});});</script>
	<nav class="navbar navbar-default header card" role="navigation" style="width: 100%;">
	<div class="container-fluid"> 
	<div class="navbar-header">
		<button type="button" class="navbar-toggle" data-toggle="collapse"
				data-target="#example-navbar-collapse">
			<span class="icon-bar"></span>
			<span class="icon-bar"></span>
			<span class="icon-bar"></span>
		</button>
		<a class="navbar-brand" href="/"><span><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="bold">C</mi><mi mathvariant="bold">A</mi><mi mathvariant="bold">I</mi><mi mathvariant="bold">J</mi><msup><mi mathvariant="bold">L</mi><mo mathvariant="bold" lspace="0em" rspace="0em">′</mo></msup><mi mathvariant="bold">s</mi><mi mathvariant="bold">B</mi><mi mathvariant="bold">L</mi><mi mathvariant="bold">O</mi><mi mathvariant="bold">G</mi></mrow><annotation encoding="application/x-tex">\mathbf{CAIJL'sBLOG}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height: 0.751892em; vertical-align: 0em;"></span><span class="mord"><span class="mord mathbf">C</span><span class="mord mathbf">A</span><span class="mord mathbf">I</span><span class="mord mathbf">J</span><span class="mord"><span class="mord mathbf">L</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height: 0.751892em;"><span class="" style="top: -3.063em; margin-right: 0.05em;"><span class="pstrut" style="height: 2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathbf mtight">′</span></span></span></span></span></span></span></span></span><span class="mord mathbf">s</span><span class="mord mathbf">B</span><span class="mord mathbf">L</span><span class="mord mathbf">O</span><span class="mord mathbf">G</span></span></span></span></span></span></a>
	</div>
	<div class="collapse navbar-collapse" id="example-navbar-collapse">
		<ul class="nav navbar-nav" style="background-color:#fcfcfc">
			<li><a href="/"><i class="menu-item-icon fa fa-fw fa-home"></i>首页</a></li>
			<li><a href="/archives/"><i class="menu-item-icon fa fa-fw fa-archive"></i>文章</a></li>
			<li><a href="/tags/"><i class="menu-item-icon fa fa-fw fa-tags"></i>标签</a></li>
			<li><a href="/settings/"><i class="menu-item-icon fa fa-fw fa-cogs"></i>设置</a></li>
			<!--li><a href="/about/"><i class="menu-item-icon fa fa-fw fa-user"></i>关于</a></li-->
			<li><a href="/games/"><i class="menu-item-icon fa fa-fw fa-gamepad"></i>其它</a></li>
			

		</ul>
	</div>
	</div>
	</nav>
<div class="container">
	<div style="height: 60px;"></div>
	<div class="row" >
		<div class="col-md-8">
			<div class="panel panel-default card" style="padding: 10px;position: relative;">
                <img src='/img/bg/44.png' style="width:100%"/>
				<span style="position: absolute;left:15px;bottom:15px;width:90%;"><font class="view-text" style="color:#fcfcfc;font-size:25px">几类有趣的数</font><br><a href="/tags/2021/" class="tag"><span  style="background-color: rgb(52, 152, 219);">2021</span></a>&nbsp;<a href="/tags/生成函数/" class="tag"><span  style="background-color: rgb(231, 76, 60);">生成函数</span></a>&nbsp;<a href="/tags/二项式反演/" class="tag"><span  style="background-color: rgb(231, 76, 60);">二项式反演</span></a>&nbsp;<a href="/tags/笔记/" class="tag"><span  style="background-color: rgb(82, 196, 26);">笔记</span></a></span>
			</div>
			<div class="panel panel-default card" style="padding: 10px;" id="main">
                <h2 id="_1">伯努利数</h2>
<p>考虑 <script type="math/tex">S(n,m)=\sum_{k=0}^{n-1}k^m</script> 的 <script type="math/tex">\mathbb{EGF}</script>
<script type="math/tex">\hat{S}(x)</script> ,还有一个神秘的 <script type="math/tex">\mathbb{EGF}</script>
<script type="math/tex">\hat{B}</script>以及 <script type="math/tex">B(i)=i![x^i]\hat{B}(x)</script>
</p>
<p>
<script type="math/tex; mode=display">\begin{aligned}
\hat{S}(x)&=\sum_{i=0}^\infty S(n,i)\frac{x^i}{i!}
=\sum_{i=0}^\infty\left(\sum_{k=0}^{n-1}k^i\right)\frac{x^i}{i!}\\
&=\sum_{k=0}^{n-1}\left(\sum_{i=0}^\infty\frac{(xk)^i}{i!}\right)=\sum_{k=0}^{n-1}\left(e^x\right)^k\\
&=\frac{e^{nx}-1}{e^x-1}=\frac{e^{nx}-1}{x}\times\frac{x}{e^x-1}\\
&=\sum_{i=1}^\infty\frac{n^i x^{i-1}}{i!}\sum_{i=0}^\infty\frac{B(i)x^i}{i!}
\end{aligned}</script>
</p>
<p>然后就可以提取系数 <script type="math/tex">[x^m]\hat{S}=\sum_{i=1}^m\frac{n^i}{i!}\times\frac{B(m-i+1)}{(m-i+1)!}</script>，也就是
<script type="math/tex; mode=display">S(n,m)=m!\sum_{i=1}^{m+1}\frac{n^iB(m-i+1)}{i!(m-i+1)}</script>
以及一种可能更优美的写法
<script type="math/tex; mode=display">S(n,m)=\frac{1}{m+1}\sum_{i=0}^m\binom{m+1}{i}n^{m-i+1}B(i)</script>
把 <script type="math/tex">n=1</script> 带入得到递推式：
<script type="math/tex; mode=display">\sum_{i=0}^m\binom{m+1}{i}B(i)=[m=0]</script>
</p>
<h2 id="_2">欧拉数</h2>
<p>定义：<script type="math/tex">\left\langle<script type="math/tex; mode=display">\begin{matrix}n\\k\end{matrix}</script>\right\rangle</script> 长度为 <script type="math/tex">n</script> 为有 <script type="math/tex">k</script> 个升高的排列数。</p>
<p>一个升高定义为使 <script type="math/tex">p_i<p_{i+1}</script> 成立的 <script type="math/tex">(p_i,p_{i+1})</script>
</p>
<p>考虑 <script type="math/tex">\rm Naive</script> 的递推式，若把 <script type="math/tex">n</script> 插到 一个 <script type="math/tex">n-1</script> 的排列中，存在两种情况：</p>
<ul>
<li>
<p>
<script type="math/tex">n</script> 插到 <script type="math/tex">(p_i,p_{i+1})</script> 中间或开头，上升数不变。从 <script type="math/tex">\left\langle<script type="math/tex; mode=display">\begin{matrix}n-1\\k\end{matrix}</script>\right\rangle</script> 转移过来，有 <script type="math/tex">k+1</script> 个位置。</p>
</li>
<li>
<p>
<script type="math/tex">n</script> 插到非上升的位置，则上升数加一。从 <script type="math/tex">\left\langle<script type="math/tex; mode=display">\begin{matrix}n-1\\k-1\end{matrix}</script>\right\rangle</script> 转移过来，有 <script type="math/tex">n-k</script> 个位置。</p>
</li>
</ul>
<p>因此我们可以得到一点也不优美的递推式：
<script type="math/tex; mode=display">\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle=(k+1)\left\langle\begin{matrix}n-1\\k\end{matrix}\right\rangle+(n-k)\left\langle\begin{matrix}n-1\\k-1\end{matrix}\right\rangle</script>
</p>
<p>这个式子复杂度是 <script type="math/tex">\mathcal{O}(n^2)</script> 的，我们希望有更快的做法。</p>
<p>恰好并不是很好做，考虑钦定 <script type="math/tex">k</script> 个上升，然后二项式反演得到最终答案。</p>
<p>一个 <script type="math/tex">(p_i,p_{i+1})</script> 使子串 <script type="math/tex">[i,i+1]</script> 是上升的。若钦定了 <script type="math/tex">k</script> 个上升，会形成 <script type="math/tex">n-k</script> 个上升的子串。设长度分别为 <script type="math/tex">a_1,a_2,a_3\ldots,a_{n-k}</script>，那么当前的答案即为：
<script type="math/tex; mode=display">\frac{n!}{\prod\limits_{i=1}^{n-k} a_i!}</script>
因为对于一个排列，每一个子串的顺序都是固定的，因此要除掉。</p>
<p>而且还应有 <script type="math/tex">\sum_{i=1}^{n-k}a_i=n</script>
</p>
<p>考虑每个串取不同数量的贡献，写成生成函数，不难发现 <script type="math/tex">\sum\limits_{i=1}^{\infty}\frac{x^i}{i!}=e^x-1</script>，于是就可以得到 <script type="math/tex">n-k</script> 个乘起来的答案：
<script type="math/tex; mode=display">
\begin{aligned}
F(x)&=(e^x-1)^{n-k}\\
&=\sum_{i=0}^{n-k}\binom{n-k}{i}e^{ix}(-1)^{n-k-i}\\
[x^n]F(x)&=\sum_{i=0}^{n-k}\binom{n-k}{i}\frac{i^n}{n!}(-1)^{n-k-i}\\
n![x^n]F(x)
&=\sum_{i=0}^{n-k}\binom{n-k}{i}i^n(-1)^{n-k-i}\\
&=\sum_{i=0}^{n-k}\frac{(n-k)!}{i!(n-k-i)!}i^n(-1)^{n-k-i}\\
&=(n-k)!\sum_{i=0}^{n-k}\frac{i^n}{i!}\times \frac{(-1)^{n-k-i}}{(n-k-i)!}
\end{aligned}
</script> 
记 <script type="math/tex">f[k]</script> 为钦定 <script type="math/tex">k</script> 个上升的排列数，<script type="math/tex">g[k]</script> 为 <script type="math/tex">\left\langle<script type="math/tex; mode=display">\begin{matrix}n\\k\end{matrix}</script>\right\rangle</script>，不难发现有：
<script type="math/tex; mode=display">f[k]=\sum_{j=k}\binom{j}{k}g[k]\Longleftrightarrow g[k]=\sum_{j=k}(-1)^{j-k}\binom{j}{k}f[k]</script>
</p>
<p>若是不要求常数的话现在是可以两次卷积的。如果要一次卷积就需要一些 <script type="math/tex">\rm Dirty\ Work</script>
</p>
<p>爆推式子：
<script type="math/tex; mode=display">\begin{aligned}
g[k]&=\sum_{j=k}(-1)^{j-k}\binom{j}{k} \sum_{i=0}^{n-j}i^n(-1)^{n-j-i}\binom{n-j}{i}\\
&=\sum_{i=0}^{n-k}i^n(-1)^{n-i-k}\sum_{j=k}\binom{j}{k}\binom{n-j}{i}\\
&=\sum_{i=0}^{n-k}i^n(-1)^{n-i-k}\binom{n+1}{i+k+1}
\end{aligned}</script>
</p>
			</div>
			<div class="panel panel-default card" style="padding: 10px;height: 50px;font-size: 20px;">
				<a style="float: left;" href="\article\P4464.html"><i class="fa fa-angle-double-left"></i></a><a style="float: right;" href="\article\new-blog.html"><i class="fa fa-angle-double-right"></i></a>
			</div>
			<div class="panel panel-default card" style="padding: 10px;font-size: 20px;" id="vcomments">
				
			</div>
			<script>
				new Valine({
					el: '#vcomments',
					appId: 'PAlFUPg0pQVTFTEo8gCB4BCf-gzGzoHsz',
					appKey: 'U38ejnLUiizJ6vLyp6ql4hRq',
					path: window.location.pathname
				})
			</script>
		</div>
		<div class="col-md-3">
				<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-info"></i>&emsp;
						<strong>文章信息</strong>
					</h3>
				</div>
                <div style="margin: 10px;">
                    <div style="margin-top: 8px;display: flex;"> 
    <span style="flex: 1 0 auto;margin-right: 6px;">标题</span>
    <span><font style="font-weight: bold">几类有趣的数</font></span>
	</div><div style="margin-top: 8px;display: flex;"> 
    <span style="flex: 1 0 auto;margin-right: 6px;">日期</span>
    <span>2021-03-10 20:40:13</span>
	</div>
                </div>
				</div>
				<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-tag"></i>&emsp;
						<strong>标签</strong>
					</h3>
				</div>
				<div style="margin: 10px;">
					<a href="/tags/2021/" class="tag"><span  style="background-color: rgb(52, 152, 219);">2021</span></a>&nbsp;<a href="/tags/生成函数/" class="tag"><span  style="background-color: rgb(231, 76, 60);">生成函数</span></a>&nbsp;<a href="/tags/二项式反演/" class="tag"><span  style="background-color: rgb(231, 76, 60);">二项式反演</span></a>&nbsp;<a href="/tags/笔记/" class="tag"><span  style="background-color: rgb(82, 196, 26);">笔记</span></a>
				</div>
				</div>
				
			<div class="panel panel-default card">
					<div class="panel-heading">
						<h3 class="panel-title">
							<i class="fa fa-user-circle-o"></i>&emsp;
							<strong>caijicjl</strong>
						</h3>
					</div>
					<div style="width: 60%;display: inline-block;padding-top: 10px;">
						<ul class="propertyLinks" style="list-style-type: none;">
							<li>
								<img style="vertical-align:middle;position:relative;top:-2px" src="/img/rating-16x16.png">
								Rating:&nbsp;
								<span style="font-weight:bold;color: gray ">312</span>
							</li>
							<li>
								<img style="vertical-align:middle;position:relative;top:-2px" src="/img/star_blue_16.png">
								Contribution:&nbsp;
								<span style="color:gray;font-weight:bold;">0</span>
							</li>
						</ul>
						<ul class="nav-links">
							<li><a href="/settings/">Settings</a></li>
							<li><a href="/archives/">Blog</a></li>
							<li><a href="/teams">Teams</a></li>
							<li><a href="/submissions/dingdingsb">Submissions</a></li>
							<li><a href="/usertalk">Talks</a></li>
							<li><a href="/contests/with/dingdingsb">Contests</a></li>
						</ul>
					</div>
					<div style="display:inline-block;vertical-align: top;margin: 10px;text-align: center;">
						<div style="height:50px;width:50px"><img src="/img/avatar.png"/></div>
						<div><a href="https://www.luogu.com.cn/user/174304" style="font-weight:bold;color:gray">caijicjl</a></div>
					</div>
				</div>
		<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-external-link"></i>&emsp;
						<strong>画中画</strong>
					</h3>
				</div>
				<div style="width:100%;margin:10px">
				<input type="text" id="url"/>
				<input value="创建" type="button" onclick="creat('kk')" /> 
				</div>
		</div>
		<script src="/js/hitokoto.js"></script>
							

				
				<span id="kk"></span>
				<div  id="myScrollspy" class="card" style="width: 100%;"  data-spy="affix">
					<script src="/js/make_toc.js"></script>
				</div>
		</div>
	</div>
 </div>
</body>
</html>
